package com.wfs.suanfa.leet;

/**
 * @author wfs
 * @date 2022-10-28 10:20
 *  八皇后问题
 */
public class EightEmpresses {
    //全局变量，小标表示行
    int[] result=new int[8];

    public static void main(String[] args) {
        EightEmpresses eightEmpresses=new EightEmpresses();
        eightEmpresses.cal8Queens(0);
    }

    public void cal8Queens(int row){
        if (row==8){
            printQueens(result);
            return; // 8行棋子都放好了，已经没法再往下递归了，所以就return
        }
        for (int column =0;column<8;++column){
            if (isOk(row,column)){
                //第row行的棋子放到column列
                result[row]=column;
                cal8Queens(row+1);
            }
        }

    }
    private boolean isOk(int row, int column) {//判断row行column列放置是否合适
        int leftup=column-1;
        int rightup=column+1;
        for (int i=row-1;i>=0;i--){
            if (result[i] ==column){
                //第i行column 列有棋子吗？
                return false;
            }
            if (leftup>=0){
                //考虑左上对角线；第i行leftUp列有棋子吗？
                if (result[i]==leftup){
                    return false;
                }
            }
            if (rightup<8){
                if (result[i] ==rightup){
                    return false;
                }
            }
            --leftup;
            ++rightup;
        }

        return true;
    }



        private void printQueens(int[] result) { // 打印出一个二维矩阵
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; ++column) {
                if (result[row] == column) System.out.print("Q ");
                else System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }


}
